#include <iostream>
#include <climits>
#include <vector>
#include <set>
#define NIL -1
struct Node{
int to, weight;
Node* next=nullptr;
Node(int _to, int _weight): to(_to), weight(_weight) {}
};
struct Vertex{
int d=INT_MAX, pi=NIL;
Vertex(){}
};
struct adjList{
int nV, nE;
Node** list;
Vertex* vertex;
adjList(int _nV, int _nE): nV(_nV), nE(_nE){
this->list=new Node*[this->nV];
this->vertex=new Vertex[this->nV];
}
~adjList(){
for(int i=0; i<this->nV; ++i) delete list[i];
delete[] list;
delete[] vertex;
}
void Insert(int u, int v, int weight){
Node* nN=new Node(v, weight);
Node* cur=this->list[u-1];
if(cur==nullptr){
list[u-1]=nN;
} else {
while(cur->next!=nullptr) cur=cur->next;
cur->next=nN;
}
}
int Weight(int u, int v){
Node* cur=this->list[u-1];
while(cur!=nullptr && cur->to!=v) cur=cur->next;
return cur->weight;
}
void InitializeSingleSource(int s){
for(int i=0; i<this->nV; ++i){
this->vertex[i].d=INT_MAX;
this->vertex[i].pi=NIL;
}
this->vertex[s-1].d=0;
}
void Relax(int u, int v){
int* Vd=&(this->vertex[v-1].d);
int weightUV=Weight(u, v), Ud=this->vertex[u-1].d;
if(*Vd==INT_MAX && Ud==INT_MAX) return;
if(*Vd>Ud+weightUV){
*Vd=Ud+weightUV;
vertex[v-1].pi=u;
}
}
};
struct QInfo{
int vertexNo;
int* value;
QInfo(int _vertexNo, int* _value): vertexNo(_vertexNo), value(_value) {}
bool operator<(const QInfo other) const{
return *(this->value) > *(other.value);
}
};
void Dijkstra(adjList* G, int s){
G->InitializeSingleSource(s);
std::set<int> S;
std::vector<QInfo> Q;
for(int i=0; i<G->nV; ++i){
Q.push_back(QInfo(i+1, &(G->vertex[i].d)));
}
while(!Q.empty()){
std::sort(Q.begin(), Q.end());
int u=Q.back().vertexNo;
Q.pop_back();
S.insert(u);
Node* cur=G->list[u-1];
if(cur==nullptr) continue;
while(cur!=nullptr){
int v=cur->to;
G->Relax(u, v);
cur=cur->next;
}
}
}
int main(void){
int vN=5, vE=10;
adjList* Graph=new adjList(vN, vE);
int eg[][3]={
{1, 2, 10}, {1, 4, 5}, {2, 3, 1}, {2, 4, 2}, {3, 5, 4},
{4, 2, 3}, {4, 3, 9}, {4, 5, 2}, {5, 1, 7}, {5, 3, 6}
};
for(int i=0; i<vE; ++i){
Graph->Insert(eg[i][0], eg[i][1], eg[i][2]);
}
Dijkstra(Graph, 1);
delete Graph;
return 0;
}